package com.cqs.leetcode.bit;

import com.cqs.leetcode.TestCaseUtils;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lixiaowen
 * @create 2019-12-21
 */
public class SingleNumberIII {


    static class Solution {
public int[] singleNumber(int[] nums) {
    int[] result = new int[2];
    int tmp = 0;
    for (int n: nums) {
        tmp = tmp ^ n;
    }
    //假定不同元素为A,B 则tmp实质为A^B
    //那么我们可以求tmp低位第一个1假定为pos
    int diff = tmp & -tmp;// 若第i位是tmp的最低位1，那么diff=1<<i; i 从0开始算
    int count = 0;
    while ((diff = diff>>1) != 0){
        count++;
    }
    //根据异或的概念，pos一定是AB互为不同的位置，那么我们用A
    //分组那么我们可以根据元素的第pos位的01情况将AB分成两个不同的组
    //而且其他重复的元素必然分到同一个组里面，只要对同一个组进行异或，就可以得到结果
    for (final int num : nums) {
        int index = (num >> count) & 1;
        result[index] = result[index] ^ num;
    }
    return result;
}

    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        List<int[]> testCase = new ArrayList<>();
        testCase.add(new int[]{1,3,1,4,5,4,7,7,0,0});
        testCase.add(new int[]{1193730082,587035181,-814709193,1676831308,-511259610,284593787,-2058511940,1970250135,-814709193,-1435587299,1308886332,-1435587299,1676831308,1403943960,-421534159,-528369977,-2058511940,1636287980,-1874234027,197290672,1976318504,-511259610,1308886332,336663447,1636287980,197290672,1970250135,1976318504,959128864,284593787,-528369977,-1874234027,587035181,-421534159,-786223891,933046536,959112204,336663447,933046536,959112204,1193730082,-786223891});
        testCase.add(new int[]{-1638685546,-2084083624,-307525016,-930251592,-1638685546,1354460680,623522045,-1370026032,-307525016,-2084083624,-930251592,472570145,-1370026032,1063150409,160988123,1122167217,1145305475,472570145,623522045,1122167217,1354460680,1145305475});
        testCase.add(new int[]{160988123,1063150409});
        testCase.add(new int[]{1403943960,959128864});
        testCase.add(new int[]{-253415037,1320283273});
        testCase.forEach(it->{
            int[] result = solution.singleNumber(it);
            System.out.println(it[0] + "\t" + Integer.toBinaryString(it[0] ) + "\t" + it[1] + "\t" + Integer.toBinaryString(it[1]) );
            System.out.println(TestCaseUtils.arrFormat(it) + "\tresult:" + TestCaseUtils.arrFormat(result));
        });

        System.out.println("---:" + (-253415037/2) + "\t " + (-253415037>>1));
        System.out.println("---:" + Integer.toBinaryString((-253415037/2)) + "\t"  + Integer.toBinaryString(-253415037>>1));
        System.out.println("---:" + Integer.toBinaryString((-3/2)) + "\t"  + Integer.toBinaryString(-3>>1));
    }
}
